package com.douma.tree;


public class _104_maximum_depth_of_binary_tree {

    int res = 0;

    public int maxDepth(TreeNode root) {
        // 最小子问题
        if (root == null) return 0;
        // 遍历左子树
        int leftMaxDepth = maxDepth(root.left);
        // 遍历右子树
        int rightMaxDepth = maxDepth(root.right);

        return Math.max(leftMaxDepth, rightMaxDepth) + 1;
    }

    // 前序遍历
    // 每次调用递归函数的时候，都是处理二叉树的某个节点
    // 二叉树的节点除了存储节点值之外，还可以存储其他属性值，比如这个节点的深度
    // 这个节点所有的信息，都是以函数参数的方式，存储在对应的栈帧中
    private void preOrder(TreeNode node, int depth) {
        // 最小子问题
        if (node == null) return;

        res = Math.max(res, depth);

        // 遍历左子树
        preOrder(node.left, depth + 1);
        // 遍历右子树
        preOrder(node.right, depth + 1);
    }


    // 后序遍历
    // 计算以 node 为根节点的二叉树的最大深度
    private int postOrder(TreeNode node) {
        // 最小子问题
        if (node == null) return 0;
        // 遍历左子树
        int leftMaxDepth = postOrder(node.left);
        // 遍历右子树
        int rightMaxDepth = postOrder(node.right);

        return Math.max(leftMaxDepth, rightMaxDepth) + 1;
    }

}
